
// ToolsLib Project

/* ToolsLib library for RusRoute firewall and other projects of
 * Andrey A. Moiseenko / IE Moiseenko A.A. (Russia)
 * e-mail: support@maasoftware.ru, maa2002@mail.ru
 * web: http://maasoftware.ru, http://maasoftware.com, http://maasoft.ru, http://maasoft.org
 * Author's full name: Andrey Alekseevitch Moiseenko
 * (russian name: Моисеенко Андрей Алексеевич)
 */

// ToolsLib/rbtree.h

/* Copyright (C) 2002-2024 Andrey A. Moiseenko (support@maasoftware.ru)
 * All rights reserved.
 *
 * This library contains cross-platform templates for working heap
 * sutable for using them in sockets' timers.
 * The library implementation written
 * by Andrey A. Moiseenko (support@maasoftware.ru).
 * This library and applications are
 * FREE FOR COMMERCIAL AND NON-COMMERCIAL USE
 * as long as the following conditions are adhered to.
 *
 * Copyright remains Andrey A. Moiseenko, and as such any Copyright notices in
 * the code are not to be removed.  If this code is used in a product,
 * Andrey A. Moiseenko should be given attribution as the author of the parts used.
 * This can be in the form of a textual message at program startup or
 * in documentation (online or textual) provided with the package.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *    This product includes software developed by Andrey A. Moiseenko (support@maasoftware.ru)
 *
 * THIS SOFTWARE IS PROVIDED BY ANDREY A. MOISEENKO ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * The licence and distribution terms for any publically available version or
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
 * copied and put under another distribution licence
 * [including the GNU Public Licence.]
 */

// Red-Black balanced tree
// Keys can be duplicated

// fixed algo from book
// Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн
// "Алгоритмы: построение и анализ. 3-е издание"
// and from 1st or second edition

#define CMAA_RB_DEBUG false
//#define CMAA_RB_DEBUG true

//#define BOOK_EX_CODE

template <class Key, class Data> class CMaaRBTree
{
protected:
    class Node
    {
    public:
        char color;
        Node * p, * left, * right;
        Key k;
        Data d;

        Node(const Key &_k, const Data &_d, int _c = 0)
        :   p(nullptr),
            left(nullptr),
            right(nullptr),
            color(_c),
            k(_k),
            d(_d)
        {
        }
        Key key()
        {
            return k;
        }
        Data & data() noexcept
        {
            return d;
        }
        const Key & c_key() const noexcept
        {
            return k;
        }
        const Data & c_data() const noexcept
        {
            return d;
        }
        ADD_UL_ALLOCATOR(Node)
//#define DEF_ALLOCATOR_CMaaRBTree(A,B) template<> CMaaFixedAllocator< CMaaRBTree< A, B >::Node >* CMaaRBTree< A, B >::Node::s_pAllocator = nullptr; template<>   CMaaFixedAllocatorCreator< CMaaRBTree< A, B >::Node > CMaaRBTree< A, B >::Node::s_AllocatorCreator(&CMaaRBTree< A, B >::Node::s_pAllocator);
  #define DEF_ALLOCATOR_CMaaRBTree(A,B) template<> CMaaFixedAllocator< CMaaRBTree< A, B >::Node >* CMaaRBTree< A, B >::Node::s_pAllocator = nullptr; template<> CMaaFixedAllocatorCreatorUl< CMaaRBTree< A, B >::Node > CMaaRBTree< A, B >::Node::s_AllocatorCreator(&CMaaRBTree< A, B >::Node::s_pAllocator);
    };
public:
    typedef Node * Handle;
    static Key key(Handle x) noexcept(noexcept(x->key()))
    {
        return x->key();
    }
    static Data & data(Handle x) noexcept
    {
        return x->data();
    }
    static const Key & c_key(Handle x) noexcept
    {
        return x->c_key();
    }
    static const Data & c_data(Handle x) noexcept
    {
        return x->c_data();
    }
    Key k(Handle x) noexcept(noexcept(x->key()))
    {
        return x->key();
    }
    Data & d(Handle x) noexcept
    {
        return x->data();
    }
    /*
    Handle GetHandle(const Key &k) const
    {
        return FindNode(k);
    }
    */

protected:
    size_t N;
    Node * _nil, * root;
    bool m_bMulti;

public:
    CMaaRBTree(bool Multi = true)
    :   m_bMulti(Multi)
    {
        N = 0;
        _nil = (Node *) TL_NEW char[sizeof(Node)];
        if  (!_nil)
        {
            throw "CMaaRBTree(): allocation error";
        }
        memset(_nil, 0, sizeof(Node));
        _nil->color = 'B';
        root = _nil;
    }
    void SimpleFree(Node * x) noexcept
    {
        if  (x != _nil)
        {
            if  (x->left != _nil)
            {
                SimpleFree(x->left);
            }
            if  (x->right != _nil)
            {
                SimpleFree(x->right);
            }
            delete x;
        }
    }
    ~CMaaRBTree()
    {
        SimpleFree(root);
        delete [] (char *)_nil;
    }
    void RemoveAll() noexcept
    {
        SimpleFree(root);
        root = _nil;
        N = 0;
        _nil->color = 'B';
    }
    size_t GetCount() const noexcept
    {
        return N;
    }
protected:
    //
    //       |        <--LeftRotate(x)--         |
    //       Y         --RightRotate(y)-->       X
    //      / \                                 / \     .
    //     X   g                               a   Y
    //    / \                                     / \   .
    //   a   b                                   b   g
    //
    void LeftRotate(Node * x) noexcept(!CMAA_RB_DEBUG)
    {
#if CMAA_RB_DEBUG
        if  (x->right == _nil)
        {
            throw "CMaaRBTree::LeftRotate(): x->right == _nil";
        }
#endif
        // x->right != nullptr
        Node * y = x->right;
        x->right = y->left;
        if  (y->left != _nil)
        {
            y->left->p = x;
        }
        y->p = x->p;
        if  (x->p == _nil)
        {
            root = y;
        }
        else if (x == x->p->left)
        {
            x->p->left = y;
        }
        else
        {
            x->p->right = y;
        }
        y->left = x;
        x->p = y;
    }
    void RightRotate(Node * y) noexcept(!CMAA_RB_DEBUG)
    {
#if CMAA_RB_DEBUG
        if  (y->left == _nil)
        {
            throw "CMaaRBTree::RightRotate(): y->left == _nil";
        }
#endif
        // y->left != nullptr
        Node * x = y->left;
        y->left = x->right;
        if  (x->right != _nil)
        {
            x->right->p = y;
        }
        x->p = y->p;
        if  (y->p == _nil)
        {
            root = x;
        }
        else if (y == y->p->right)
        {
            y->p->right = x;
        }
        else
        {
            y->p->left = x;
        }
        x->right = y;
        y->p = x;
    }
public:
    // 0 - ok
    int Add(const Key& k, const Data& d)
    {
        return RBInsert(k, d, m_bMulti) ? 0 : 1;
    }
    // Handle != nullptr - ok
    Handle AddNode(const Key& k, const Data& d)
    {
        return RBInsert(k, d, m_bMulti);
    }
    // Handle != nullptr - ok
    Node* Insert(const Key& k, const Data& d)
    {
        return RBInsert(k, d, m_bMulti);
    }

    // specific multi
    // 0 - ok
    int Add(const Key& k, const Data& d, bool bMulti)
    {
        return RBInsert(k, d, bMulti) ? 0 : 1;
    }
    // Handle != nullptr - ok
    Handle AddNode(const Key& k, const Data& d, bool bMulti)
    {
        return RBInsert(k, d, bMulti);
    }
    // Handle != nullptr - ok
    Node * Insert(const Key &k, const Data &d, bool bMulti)
    {
        return RBInsert(k, d, bMulti);
    }

    int GetHeightSlow(Node* x = nullptr) const noexcept
    {
        if  (!x)
        {
            x = root;
        }
        if  (x == _nil)
        {
            return 0;
        }
        const int l = GetHeightSlow(x->left);
        const int r = GetHeightSlow(x->right);
        return 1 + (l > r ? l : r);
    }
    // RB-Insert(T,z)
    // both book & wiki are ok
    Node * RBInsert(const Key &k, const Data &d, bool bMulti)
    {
        /*
        if (!bMulti)
        {
            Handle r = FindNode(k);
            if (r)
            {
                return nullptr;
            }
        }
        */
        Node * y = _nil;
        Node * x = root;
        if  (!bMulti)
        {
            while(x != _nil)
            {
                y = x;
                if  (k < x->k)
                {
                    x = x->left;
                }
                else if (x->k == k)
                {
                    return nullptr;
                }
                else
                {
                    x = x->right;
                }
            }
        }
        else
        {
            while(x != _nil)
            {
                y = x;
                if  (k < x->k)
                {
                    x = x->left;
                }
                else
                {
                    x = x->right;
                }
            }
        }
        //Node * z = TL_NEW Node(k, d, 'R');
        Node* z = TL_NEW Node(k, d, 'R');
        //z->p = z->left = z->right =_nil;
        z->p = y;
        if  (y == _nil)
        {
            root = z;
        }
        else if (z->k < y->k)
        {
            y->left = z;
        }
        else
        {
            y->right = z;
        }
        z->left = _nil;
        z->right = _nil;
        z->color = 'R';
        N++;
        //Print();
        RBInsertFixup(z);
        return z;
    }
protected:
    void RBInsertFixup(Node *z)
    {
        while(z->p->color == 'R')
        {
            if  (z->p == root)
            {
                //throw "CMaaRBTree::RBInsertFixup(): (z->p == root)";
                break;
            }
            if  (z->p == z->p->p->left)
            {
                Node * y = z->p->p->right;
                if  (y->color == 'R') // wiki: if (y != nullptr && y->color == 'R')
                {
                    z->p->color = 'B';
                    y->color = 'B';
                    z->p->p->color = 'R';
                    z = z->p->p;
                    //__utf8_printf(">1<\n");
                    //Print();
                    continue;
                }
                if  (z == z->p->right) // wiki: if (z == z->p->right && z->p == z->p->p->left)
                {
                    z = z->p;
                    LeftRotate(z);
                    //__utf8_printf(">2<\n");
                    //Print();
                }
                z->p->color = 'B';
                z->p->p->color = 'R';
                // wiki: if (z == z->p->left && z->p == z->p->p->left)
                RightRotate(z->p->p);
                // wiki: else
                // wiki: LeftRotate(z->p->p);

                //__utf8_printf(">3<\n");
                //Print();
                //break;
            }
            else //if (z->p == z->p->p->right)
            {
                Node * y = z->p->p->left;
                if  (y->color == 'R')
                {
                    z->p->color = 'B';
                    y->color = 'B';
                    z->p->p->color = 'R';
                    z = z->p->p;
                    //__utf8_printf(">1<\n");
                    //Print();
                    continue;
                }
                if  (y->color == 'B' && z == z->p->left)
                {
                    z = z->p;
                    RightRotate(z);
                    //__utf8_printf(">2<\n");
                    //Print();
                }
                z->p->color = 'B';
                z->p->p->color = 'R';
                LeftRotate(z->p->p);
                //__utf8_printf(">3<\n");
                //Print();
                //break;
            }
            //else
            //{
            //throw "CMaaRBTree::RBInsertFixup(): (z->p != z->p->p->left) && (z->p != z->p->p->right)";
            //}
            break;
        }
        root->color = 'B';
    }
protected:
    Node * grandparent(Node *n) noexcept
    {
        if  (n != _nil && n->p != _nil)
        {
            return n->p->p;
        }
        else
        {
            return _nil;
        }
    }
    Node * uncle(Node *n) noexcept
    {
        Node * g = grandparent(n);
        if  (g == _nil)
        {
            return _nil; // No grandparent means no uncle
        }
        if  (n->p == g->left)
        {
            return g->right;
        }
        else
        {
            return g->left;
        }
    }
    void rotate_left(Node *n) noexcept
    {
        Node *pivot = n->right;

        pivot->p = n->p; // при этом, возможно, pivot становится корнем дерева
        if  (n->p != _nil)
        {
            if  (n->p->left == n)
            {
                n->p->left = pivot;
            }
            else
            {
                n->p->right = pivot;
            }
        }
        else
        {
            root = pivot;
        }

        n->right = pivot->left;
        if  (pivot->left != _nil)
        {
            pivot->left->p = n;
        }

        n->p = pivot;
        pivot->left = n;
    }

    void rotate_right(Node *n) noexcept
    {
        Node *pivot = n->left;

        pivot->p = n->p; // при этом, возможно, pivot становится корнем дерева
        if  (n->p != _nil)
        {
            if  (n->p->left == n)
            {
                n->p->left = pivot;
            }
            else
            {
                n->p->right = pivot;
            }
        }
        else
        {
            root = pivot;
        }

        n->left = pivot->right;
        if  (pivot->right != _nil)
        {
            pivot->right->p = n;
        }
        n->p = pivot;
        pivot->right = n;
    }
    void insert_case1(Node *n) noexcept
    {
        if  (n->p == _nil)
        {
            n->color = 'B';
        }
        else
        {
            insert_case2(n);
        }
    }
    void insert_case2(Node *n) noexcept
    {
        if  (n->p->color == 'B')
        {
            return; // Tree is still valid
        }
        else
        {
            insert_case3(n);
        }
    }
    void insert_case3(Node *n) noexcept
    {
        Node *u = uncle(n), * g;

        if  (u != _nil && u->color == 'R')
        {
            // && (n->parent->color == RED) Второе условие проверяется в insert_case2, то есть родитель уже является красным.
            n->p->color = 'B';
            u->color = 'B';
            g = grandparent(n);
            g->color = 'R';
            insert_case1(g);
        }
        else
        {
            insert_case4(n);
        }
    }
    void insert_case4(Node *n) noexcept
    {
        Node *g = grandparent(n);

        if  (n == n->p->right && n->p == g->left)
        {
            rotate_left(n->p);

            /*
             * rotate_left может быть выполнен следующим образом, учитывая что уже есть *g =  grandparent(n) 
             *
             * struct node *saved_p=g->left, *saved_left_n=n->left;
             * g->left=n; 
             * n->left=saved_p;
             * saved_p->right=saved_left_n;
             * 
             */

            n = n->left;
        }
        else if (n == n->p->left && n->p == g->right)
        {
            rotate_right(n->p);

            /*
             * rotate_right может быть выполнен следующим образом, учитывая что уже есть *g =  grandparent(n) 
             *
             * struct node *saved_p=g->right, *saved_right_n=n->right;
             * g->right=n; 
             * n->right=saved_p;
             * saved_p->left=saved_right_n;
             * 
             */

            n = n->right;
        }
        insert_case5(n);
    }

    void insert_case5(Node *n) noexcept
    {
        Node *g = grandparent(n);

        n->p->color = 'B';
        g->color = 'R';
        if  (n == n->p->left && n->p == g->left)
        {
            rotate_right(g);
        }
        else
        {
            // (n == n->p->right) && (n->p == g->right)
            rotate_left(g);
        }
    }

    // ins_fixup() is iterative version of insert_case1() - insert_case5(), written by Moiseenko A.A.
    void ins_fixup(Node *n) noexcept
    {
        while(1)
        {
            if  (n->p == _nil)
            {
                n->color = 'B';
                break;
            }
            if  (n->p->color == 'B')
            {
                break; // Tree is still valid
            }

            Node *u = uncle(n), * g;

            if  (u != _nil && u->color == 'R')
            {
                // && (n->parent->color == RED) Второе условие проверяется в insert_case2, то есть родитель уже является красным.
                n->p->color = 'B';
                u->color = 'B';
                g = grandparent(n);
                g->color = 'R';
                n = g;
                continue;
            }
            g = grandparent(n);

            if  (n == n->p->right && n->p == g->left)
            {
                rotate_left(n->p);

                /*
                 * rotate_left может быть выполнен следующим образом, учитывая что уже есть *g =  grandparent(n) 
                 *
                 * struct node *saved_p=g->left, *saved_left_n=n->left;
                 * g->left=n; 
                 * n->left=saved_p;
                 * saved_p->right=saved_left_n;
                 *
                 */

                n = n->left;
            }
            else if (n == n->p->left && n->p == g->right)
            {
                rotate_right(n->p);

                /*
                 * rotate_right может быть выполнен следующим образом, учитывая что уже есть *g =  grandparent(n) 
                 *
                 * struct node *saved_p=g->right, *saved_right_n=n->right;
                 * g->right=n; 
                 * n->right=saved_p;
                 * saved_p->left=saved_right_n;
                 *
                 */

                n = n->right;
            }
            g = grandparent(n);

            n->p->color = 'B';
            g->color = 'R';
            if  (n == n->p->left && n->p == g->left)
            {
                rotate_right(g);
            }
            else
            {
                // (n == n->p->right) && (n->p == g->right)
                rotate_left(g);
            }
            break;
        }
    }

public:
    Node * RBInsertWiki(const Key &k, const Data &d, bool bMulti)
    {
        /*
        if (!bMulti)
        {
            Handle r = FindNode(k);
            if (r)
            {
                return nullptr;
            }
        }
        */
        Node * y = _nil;
        Node * x = root;
        if  (!bMulti)
        {
            while(x != _nil)
            {
                y = x;
                if  (k < x->k)
                {
                    x = x->left;
                }
                else if (x->k == k)
                {
                    return nullptr;
                }
                else
                {
                    x = x->right;
                }
            }
        }
        else
        {
            while(x != _nil)
            {
                y = x;
                if  (k < x->k)
                {
                    x = x->left;
                }
                else
                {
                    x = x->right;
                }
            }
        }
        //Node * z = TL_NEW Node(k, d, 'R');
        Node* z = TL_NEW Node(k, d, 'R');
        //z->p = z->left = z->right =_nil;
        z->p = y;
        if  (y == _nil)
        {
            root = z;
        }
        else if (z->k < y->k)
        {
            y->left = z;
        }
        else
        {
            y->right = z;
        }
        z->left = _nil;
        z->right = _nil;
        z->color = 'R';
        N++;
        //RBInsertFixup(z);
        //insert_case1(z);
        ins_fixup(z);
        return z;
    }

protected:
#ifdef BOOK_EX_CODE
    void RBTransplant(Node * u, Node * v) noexcept
    {
        if  (u->p == _nil)
        {
            root = v;
        }
        else if (u == u->p->left)
        {
            u->p->left = v;
        }
        else
        {
            u->p->right = v;
        }
        v->p = u->p;
    }
#endif
public:
    Node * begin() const noexcept
    {
        return root != _nil ? TreeMinimum(root) : _nil;
    }
    // next:  p = rb.TreeSuccessor(p);
    // for (CMaaRBTree<int, int>::Handle p = r.begin(); p != r.end(); p = r.TreeSuccessor(p))
    Node * end() const noexcept
    {
        return _nil;
    }
    Node * rbegin() const noexcept
    {
        return root != _nil ? TreeMaximum(root) : _nil;
    }
    // prev:  p = rb.TreePredecessor(p);
    // for (CMaaRBTree<int, int>::Handle p = r.begin(); p != r.end(); p = r.TreePredecessor(p))
    Node * rend() const noexcept
    {
        return _nil;
    }
    Node * TreeMinimum(Node * x) const noexcept
    {
        while(x->left != _nil)
        {
            x = x->left;
        }
        return x;
    }
    Node * TreeMaximum(Node * x) const noexcept
    {
        while(x->right != _nil)
        {
            x = x->right;
        }
        return x;
    }
    Node * TreeSuccessor(Node * x) const noexcept
    {
        if  (x->right != _nil)
        {
            return TreeMinimum(x->right);
        }
        Node * y = x->p;
        while(y != _nil && x == y->right)
        {
            x = y;
            y = y->p;
        }
        return y;
    }
    Node * TreePredecessor(Node * x) const noexcept
    {
        if  (x->left != _nil)
        {
            return TreeMaximum(x->left);
        }
        Node * y = x->p;
        while(y != _nil && x == y->left)
        {
            x = y;
            y = y->p;
        }
        return y;
    }
    Node* TreeSuccessor(Node* x, Node* p) const noexcept
    {
        if  (x->right != _nil)
        {
            return TreeMinimum(x->right);
        }
        if  (x == p)
        {
            return _nil;
        }
        Node* y = x->p;
        while(y != _nil && x == y->right)
        {
            if  (y == p)
            {
                return _nil;
            }
            x = y;
            y = y->p;
        }
        return y;
    }
    Node* TreePredecessor(Node* x, Node* p) const noexcept
    {
        if  (x->left != _nil)
        {
            return TreeMaximum(x->left);
        }
        if  (x == p)
        {
            return _nil;
        }
        Node* y = x->p;
        while(y != _nil && x == y->left)
        {
            if  (y == p)
            {
                return _nil;
            }
            x = y;
            y = y->p;
        }
        return y;
    }
    Node * RecursiveTreeSearch(Node * x, const Key &k) const noexcept(noexcept(k == x->k) && noexcept(k < x->k))
    {
        if  (x == _nil || k == x->k)
        {
            return x;
        }
        if  (k < x->k)
        {
            return RecursiveTreeSearch(x->left, k);
        }
        else
        {
            return RecursiveTreeSearch(x->right, k);
        }
    }
    Node * IteractiveTreeSearch(Node * x, const Key &k) const noexcept(noexcept(k == x->k) && noexcept(k < x->k))
    {
        while(x != _nil && !(k == x->k))
        {
            if  (k < x->k)
            {
                x = x->left;
            }
            else
            {
                x = x->right;
            }
        }
        return x;
    }
    Node * TreeSearchLQ(const Key &k, bool bRetEq = true, Node * x = nullptr) const noexcept(noexcept(k == x->k) && noexcept(k < x->k))
    {
        x = x ? x : root;
        Node * y;
        if  (bRetEq)
        {
            y = IteractiveTreeSearch(x, k);
            if  (y != _nil)
            {
                if  (m_bMulti)
                {
                    while(1)
                    {
                        Node* z = TreeSuccessor(y, x);
                        if  (z != _nil && k == z->k)
                        {
                            y = z;
                        }
                        else
                        {
                            break;
                        }
                    }
                }
                return y;
            }
        }
        y = _nil;

        while(x != _nil)
        {
            if  (k == x->k)
            {
                x = x->left;
            }
            else if (k < x->k)
            {
                x = x->left;
            }
            else
            {
                y = x;
                x = x->right;
            }
        }
        return y;
    }
    Node * TreeSearchGQ(const Key &k, bool bRetEq = true, Node * x = nullptr) const noexcept(noexcept(k == x->k) && noexcept(k < x->k))
    {
        x = x ? x : root;
        Node * y;
        if  (bRetEq)
        {
            y = IteractiveTreeSearch(x, k);
            if  (y != _nil)
            {
                if  (m_bMulti)
                {
                    while(1)
                    {
                        Node* z = TreePredecessor(y, x);
                        if  (z != _nil && k == z->k)
                        {
                            y = z;
                        }
                        else
                        {
                            break;
                        }
                    }
                }

                return y;
            }
        }
        y = _nil;

        while(x != _nil)
        {
            if  (k == x->k)
            {
                x = x->right;
            }
            else if (k < x->k)
            {
                y = x;
                x = x->left;
            }
            else
            {
                x = x->right;
            }
        }
        return y;
    }
    /*
    Node * TreeSearchLQ1(const Key &k, bool bRetEq = true)
    {
        Node * x = root, * y = _nil;

        while(x != _nil)
        {
            if   (k == x->k)
            {
                if   (bRetEq)
                {
                    return x;
                }
                while(x != _nil && x->k == k)
                {
                    x = TreePredecessor(x);
                }
                return x;
            }
            if   (k < x->k)
            {
                x = x->left;
            }
            else
            {
                y = x;
                x = x->right;
            }
        }
        return y;
    }
    Node * TreeSearchGQ1(const Key &k, bool bRetEq = true)
    {
        Node * x = root, * y = _nil;

        while(x != _nil)
        {
            if   (k == x->k)
            {
                if   (bRetEq)
                {
                    return x;
                }
                while(x != _nil && x->k == k)
                {
                    x = TreeSuccessor(x);
                }
                return x;
            }
            if   (k < x->k)
            {
                y = x;
                x = x->left;
            }
            else
            {
                x = x->right;
            }
        }
        return y;
    }
    */
    int Find(const Key &k, Data *d = nullptr) noexcept(noexcept(IteractiveTreeSearch(root, k)) && noexcept(*d = *d))
    {
        Node * x = IteractiveTreeSearch(root, k);
        if  (x != _nil)
        {
            if  (d)
            {
                *d = x->d;
            }
            return 0;
        }
        return 1;
    }
    Handle FindNode(const Key &k) const noexcept(noexcept(IteractiveTreeSearch(root, k))) //noexcept(noexcept(Key::operator==) && noexcept(Key::operator<))
    {
        Node * x = IteractiveTreeSearch(root, k);
        return x != _nil ? x : nullptr;
    }
    int Remove(const Key &k, Data *d = nullptr) noexcept(noexcept(IteractiveTreeSearch(root, k)) && !CMAA_RB_DEBUG)
    {
        Node * x = IteractiveTreeSearch(root, k);
        if  (x != _nil)
        {
            if  (d)
            {
                *d = x->d;
            }
            RBDelete(x);
            return 0;
        }
        return 1;
    }
    int FindMin(Key *k = nullptr, Data *d = nullptr) const noexcept
    {
        Node * x = TreeMinimum(root);
        if  (x != _nil)
        {
            if  (k)
            {
                *k = x->k;
            }
            if  (d)
            {
                *d = x->d;
            }
            return 0;
        }
        return 1;
    }
    int FindMax(Key *k = nullptr, Data *d = nullptr) const noexcept
    {
        Node * x = TreeMaximum(root);
        if  (x != _nil)
        {
            if  (k)
            {
                *k = x->k;
            }
            if  (d)
            {
                *d = x->d;
            }
            return 0;
        }
        return 1;
    }
    int FindSucc(const Key &_k, Key *k = nullptr, Data *d = nullptr) const noexcept(noexcept(IteractiveTreeSearch(root, _k)) && noexcept(*k = *k) && noexcept(*d = *d))
    {
        Node * x = IteractiveTreeSearch(root, _k);
        if  (x != _nil)
        {
            x = TreeSuccessor(x);
            if  (x != _nil)
            {
                if  (k)
                {
                    *k = x->k;
                }
                if  (d)
                {
                    *d = x->d;
                }
                return 0;
            }
            return 2;
        }
        return 1;
    }
    int FindPred(const Key &_k, Key *k = nullptr, Data *d = nullptr) const noexcept(noexcept(IteractiveTreeSearch(root, _k)) && noexcept(*k = *k) && noexcept(*d = *d))
    {
        Node * x = IteractiveTreeSearch(root, _k);
        if  (x != _nil)
        {
            x = TreePredecessor(x);
            if  (x != _nil)
            {
                if  (k)
                {
                    *k = x->k;
                }
                if  (d)
                {
                    *d = x->d;
                }
                return 0;
            }
            return 2;
        }
        return 1;
    }
    Handle FindSucc(Handle x) const noexcept
    {
        if  (x && x != _nil)
        {
            x = TreeSuccessor(x);
            return x != _nil ? x : nullptr;
        }
        return nullptr;
    }
    Handle FindPred(Handle x) const noexcept
    {
        if  (x && x != _nil)
        {
            x = TreePredecessor(x);
            return x != _nil ? x : nullptr;
        }
        return nullptr;
    }
    // 0 - ok
    int FindLQ(const Key &_k, bool bRetEq, Key *k = nullptr, Data *d = nullptr) const noexcept(noexcept(TreeSearchLQ(_k, bRetEq, root) && noexcept(*k = *k) && noexcept(*d = *d)))
    {
        Node * x = TreeSearchLQ(_k, bRetEq, root);
        if  (x != _nil)
        {
            if  (k)
            {
                *k = x->k;
            }
            if  (d)
            {
                *d = x->d;
            }
            return 0;
        }
        return 1;
    }
    // 0 - ok
    int FindGQ(const Key &_k, bool bRetEq, Key *k = nullptr, Data *d = nullptr) const noexcept(noexcept(TreeSearchGQ(_k, bRetEq, root) && noexcept(*k = *k) && noexcept(*d = *d)))
    {
        Node * x = TreeSearchGQ(_k, bRetEq, root);
        if  (x != _nil)
        {
            if  (k)
            {
                *k = x->k;
            }
            if  (d)
            {
                *d = x->d;
            }
            return 0;
        }
        return 1;
    }
    // 0 - ok
    int FindLQ(const Key &_k, Key *k = nullptr, Data *d = nullptr) const noexcept(noexcept(FindLQ(_k, true, k, d)))
    {
        return FindLQ(_k, true, k, d);
    }
    // 0 - ok
    int FindGQ(const Key &_k, Key *k = nullptr, Data *d = nullptr) const noexcept(noexcept(FindGQ(_k, true, k, d)))
    {
        return FindGQ(_k, true, k, d);
    }
    // 0 - ok
    int FindLnQ(const Key &_k, Key *k = nullptr, Data *d = nullptr) const noexcept(noexcept(FindLQ(_k, true, k, d)))
    {
        return FindLQ(_k, false, k, d);
    }
    // 0 - ok
    int FindGnQ(const Key &_k, Key *k = nullptr, Data *d = nullptr) const noexcept(noexcept(FindGQ(_k, true, k, d)))
    {
        return FindGQ(_k, false, k, d);
    }
protected:
public:
    void RBDelete(Node * z) noexcept(!CMAA_RB_DEBUG)
    {
        //RBDelete1(z);
        RBDeleteWiki(z);
    }
#ifdef BOOK_EX_CODE
    // 3rd edition, bad
    void RBDelete3(Node * z)
    {
        Node * y = z;
        Node * x;
        char y_original_color = y->color;
        if  (z->left == _nil)
        {
            x = z->right;
            RBTransplant(z, z->right);
            /*
            if (y_original_color == 'B' && x == _nil && z->p != _nil && z->p->p != _nil)
            {
                LeftRotate(z->p->p);
                root->color = 'B';
            }
            */
        }
        else if (z->right == _nil)
        {
            x = z->left;
            RBTransplant(z, z->left);
            /*
            if (y_original_color == 'B' && x == _nil && z->p != _nil && z->p->p != _nil)
            {
                RightRotate(z->p->p);
                root->color = 'B';
            }
            */
        }
        else
        {
            y = TreeMinimum(z->right);
            y_original_color = y->color;
            x = y->right;
            if  (y->p == z)
            {
                x->p = y;
            }
            else
            {
                RBTransplant(y, y->right);
                y->right = z->right;
                y->right->p = y;
            }
            RBTransplant(z, y);
            y->left = z->left;
            y->left->p = y;
            y->color = z->color;
        }
        if  (y_original_color == 'B' && x != _nil)
        {
            RBDeleteFixup(x);
        }
        N--;
        delete z;
    }
    // 1st edition, bad
    void RBDelete1(Node * z)
    {
        Node * y;
        if  (z->left == _nil || z->right == _nil)
        {
            y = z;
        }
        else
        {
            y = TreeSuccessor(z);
        }
        Node * x;
        if  (y->left != _nil)
        {
            x = y->left;
        }
        else
        {
            x = y->right;
        }
        x->p = y->p;
        if  (y->p == _nil)
        {
            root = x;
        }
        else if (y == y->p->left)
        {
            y->p->left = x;
        }
        else
        {
            y->p->right = x;
        }
        char y_orig_color = y->color;
        if  (y != z)
        {
            y->p = z->p;
            y->left = z->left;
            y->right = z->right;
            y->color = z->color;
            y->left->p = y;
            y->right->p = y;
            if  (z == root)
            {
                root = y;
                root->color = 'B';
            }
            else if (z->p->left == z)
            {
                z->p->left = y;
            }
            else
            {
                z->p->right = y;
            }
        }
        if  (y_orig_color == 'B' && x != _nil)
        {
            //__utf8_printf("fixup...\n");
            RBDeleteFixup(x);
        }
        N--;
        delete z;
    }
#endif
    // Wiki 26-27.12.2017
    // https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B0%D1%81%D0%BD%D0%BE-%D1%87%D1%91%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE
    Node * Sibling(Node * n) noexcept
    {
        if  (n == n->p->left)
        {
            return n->p->right;
        }
        else
        {
            return n->p->left;
        }
    }
    void RBDeleteWiki(Node * z) noexcept(!CMAA_RB_DEBUG)
    {
        if  (z->left != _nil && z->right != _nil)
        {
            Node * y = TreeSuccessor(z);
            //swap(*y, *z);
            CMaaSwap(y->p, z->p);
            if  (y->p == _nil)
            {
                root = y;
            }
            else
            {
                if  (y->p->left == z)
                {
                    y->p->left = y;
                }
                else
                {
                    y->p->right = y;
                }
            }
            if  (z->p->left == y)
            {
                z->p->left = z;
            }
            else
            {
                z->p->right = z;
            }
            CMaaSwap(y->left, z->left);
            CMaaSwap(y->right, z->right);
            CMaaSwap(y->color, z->color);
            y->left->p = y;
            y->right->p = y;
            z->left->p = z;
            z->right->p = z;
            //root->color = 'B';
        }
#if CMAA_RB_DEBUG
        if  (z->left != _nil && z->right != _nil)
        {
            throw "if (z->left != _nil && z->right != _nil)";
        }
#endif
        //rm0(z); // recursive fixup
        rm_fixup(z); // iterative fixup
        N--;
        delete z;
    }
protected:
    // rm0() - rm6() - wiki source
    void rm0(Node *n) noexcept(!CMAA_RB_DEBUG)
    {
#if CMAA_RB_DEBUG
        if  (n->left != _nil && n->right != _nil)
        {
            throw "if (n->left != _nil && n->right != _nil)";
        }
#endif
        Node * c = n->left != _nil ? n->left : n->right;
        //replace_node(n, c); // n <== c
        c->p = n->p;
        if  (c->p == _nil)
        {
            root = c;
        }
        else
        {
            if  (c->p->left == n)
            {
                c->p->left = c;
            }
            else
            {
                c->p->right = c;
            }
        }
        n->left = n->right = n->p = _nil;
        if  (n->color == 'B')
        {
            if  (c->color == 'R')
            {
                c->color = 'B';
            }
            else
            {
                rm1(c);
            }
        }
        // delete n;
    }
    void rm1(Node * n) noexcept(!CMAA_RB_DEBUG)
    {
        if  (n->p != _nil)
        {
            rm2(n);
        }
    }
    void rm2(Node * n) noexcept(!CMAA_RB_DEBUG)
    {
        Node * s = Sibling(n);
        if  (s->color == 'R')
        {
            n->p->color = 'R';
            s->color = 'B';
            if  (n == n->p->left)
            {
                LeftRotate(n->p);
            }
            else
            {
                RightRotate(n->p);
            }
        }
        rm3(n);
    }
    void rm3(Node * n) noexcept(!CMAA_RB_DEBUG)
    {
        Node *s = Sibling(n);

        if  (n->p->color == 'B' && s->color == 'B' &&
            s->left->color == 'B' && s->right->color == 'B')
        {
            s->color = 'R';
            rm1(n->p);
        }
        else
        {
            rm4(n);
        }
    }
    void rm4(Node *n) noexcept(!CMAA_RB_DEBUG)
    {
        Node *s = Sibling(n);

        if  (n->p->color == 'R' && s->color == 'B' &&
            s->left->color == 'B' && s->right->color == 'B')
        {
            s->color = 'R';
            n->p->color = 'B';
        }
        else
        {
            rm5(n);
        }
    }
    void rm5(Node *n) noexcept(!CMAA_RB_DEBUG)
    {
        Node *s = Sibling(n);

        if  (s->color == 'B')
        {
            /* this if statement is trivial,
               due to case 2 (even though case 2 changed the sibling to a sibling's child,
               the sibling's child can't be red, since no red parent can have a red child). */
            /* the following statements just force the red to be on the left of the left of the parent,
               or right of the right, so case six will rotate correctly. */
            if  (n == n->p->left && s->right->color == 'B' && s->left->color == 'R')
            {
                /* this last test is trivial too due to cases 2-4. */
                s->color = 'R';
                s->left->color = 'B';
                RightRotate(s);
            }
            else if (n == n->p->right && s->left->color == 'B' && s->right->color == 'R')
            {
                /* this last test is trivial too due to cases 2-4. */
                s->color = 'R';
                s->right->color = 'B';
                LeftRotate(s);
            }
        }
        rm6(n);
    }
    void rm6(Node *n) noexcept(!CMAA_RB_DEBUG)
    {
        Node *s = Sibling(n);

        s->color = n->p->color;
        n->p->color = 'B';

        if  (n == n->p->left)
        {
            s->right->color = 'B';
            LeftRotate(n->p);
        }
        else
        {
            s->left->color = 'B';
            RightRotate(n->p);
        }
    }

    // rm_fixup() is iterative version of rm0() - rm6(), written by Moiseenko A.A.
    void rm_fixup(Node *n) noexcept(!CMAA_RB_DEBUG)
    {
#if CMAA_RB_DEBUG
        if  (n->left != _nil && n->right != _nil) // assert
        {
            throw "if (n->left != _nil && n->right != _nil)";
        }
#endif
        Node * c = n->left != _nil ? n->left : n->right;
        //replace_node(n, c); // n <== c
        c->p = n->p;
        if  (c->p == _nil)
        {
            root = c;
        }
        else
        {
            if  (c->p->left == n)
            {
                c->p->left = c;
            }
            else
            {
                c->p->right = c;
            }
        }
        n->left = n->right = n->p = _nil;
        if  (n->color == 'B')
        {
            if  (c->color == 'R')
            {
                c->color = 'B';
            }
            else
            {
                //rm1(c);
                n = c;
                while(n->p != _nil)
                {
                    //rm2(n);

                    Node * s = Sibling(n);
                    if  (s->color == 'R')
                    {
                        n->p->color = 'R';
                        s->color = 'B';
                        if  (n == n->p->left)
                        {
                            LeftRotate(n->p);
                        }
                        else
                        {
                            RightRotate(n->p);
                        }
                    }
                    //rm3(n);
                    s = Sibling(n);

                    if  (n->p->color == 'B' && s->color == 'B' && s->left->color == 'B' && s->right->color == 'B')
                    {
                        s->color = 'R';
                        //rm1(n->p);
                        n = n->p;
                        continue;
                    }
                    //rm4(n);
                    //s = Sibling(n);

                    if  (n->p->color == 'R' && s->color == 'B' && s->left->color == 'B' && s->right->color == 'B')
                    {
                        s->color = 'R';
                        n->p->color = 'B';
                    }
                    else
                    {
                        //rm5(n);
                        //Node *s = Sibling(n);

                        if  (s->color == 'B')
                        {
                            /* this if statement is trivial,
                               due to case 2 (even though case 2 changed the sibling to a sibling's child,
                               the sibling's child can't be red, since no red parent can have a red child). */
                            /* the following statements just force the red to be on the left of the left of the parent,
                               or right of the right, so case six will rotate correctly. */
                            if  (n == n->p->left && s->right->color == 'B' && s->left->color == 'R')
                            {
                                /* this last test is trivial too due to cases 2-4. */
                                s->color = 'R';
                                s->left->color = 'B';
                                RightRotate(s);
                            }
                            else if (n == n->p->right && s->left->color == 'B' && s->right->color == 'R')
                            {
                                /* this last test is trivial too due to cases 2-4. */
                                s->color = 'R';
                                s->right->color = 'B';
                                LeftRotate(s);
                            }
                        }
                        //rm6(n);
                        s = Sibling(n);

                        s->color = n->p->color;
                        n->p->color = 'B';

                        if  (n == n->p->left)
                        {
                            s->right->color = 'B';
                            LeftRotate(n->p);
                        }
                        else
                        {
                            s->left->color = 'B';
                            RightRotate(n->p);
                        }
                    }
                    break;
                }
            }
        }
        // delete orig n in called fn;
    }
#ifdef BOOK_EX_CODE
    // bad
    void RBDeleteFixup(Node * x) noexcept(!CMAA_RB_DEBUG)
    {
        while(x != root && x->color == 'B')
        {
            if  (x == x->p->left)
            {
                Node * w = x->p->right;
                if  (w->color == 'R')
                {
                    w->color = 'B';             // 1
                    x->p->color = 'R';          // 1
                    LeftRotate(x->p);           // 1
                    w = x->p->right;            // 1
                }
                if  (w == _nil)
                {
                    break; // wiki: none
                }
                // wiki: if (x->p->color == 'B' && w->color == 'B' && w->left->color == 'B' && w->right->color == 'B')
                if  (w->left->color == 'B' && w->right->color == 'B')
                {
                    w->color = 'R';             // 2
                    x = x->p;                   // 2
                }
                else
                {
                    // далее несоответствие
                    if  (w->right->color == 'B')
                    {
                        w->left->color = 'B'; // n  // 3
                        // nw.color = 'R'
                        w->color = 'R';             // 3
                        RightRotate(w);             // 3
                        w = x->p->right;            // 3
                    }
                    w->color = x->p->color;     // 4
                    x->p->color = 'B';          // 4
                    w->right->color = 'B';      // 4
                    LeftRotate(x->p);           // 4
                    x = root;                   // 4
                }
            }
            else if (x == x->p->right)
            {
                Node * w = x->p->left;
                if  (w->color == 'R')
                {
                    w->color = 'B';             // 1
                    x->p->color = 'R';          // 1
                    RightRotate(x->p);          // 1
                    w = x->p->left;             // 1
                }
                if  (w == _nil)
                {
                    break;
                }
                if  (w->right->color == 'B' && w->left->color == 'B')
                {
                    w->color = 'R';             // 2
                    x = x->p;                   // 2
                }
                else
                {
                    if  (w->left->color == 'B')
                    {
                        w->right->color = 'B'; // n // 3
                        // nw.color = 'R'
                        w->color = 'R';             // 3
                        LeftRotate(w);              // 3
                        w = x->p->left;             // 3
                    }
                    w->color = x->p->color;     // 4
                    x->p->color = 'B';          // 4
                    w->left->color = 'B';       // 4
                    RightRotate(x->p);          // 4
                    x = root;                   // 4
                }
            }
        }
        x->color = 'B';
    }
#endif
public:
    void Swap(CMaaRBTree<Key, Data> &That) noexcept
    {
        CMaaSwap(N, That.N);
        CMaaSwap(_nil, That._nil);
        CMaaSwap(root, That.root);
        CMaaSwap(m_bMulti, That.m_bMulti);
    }
    CMaaString Node2Text(Node* x);
    //{
    //   return CMaaString::sFormat("%d%c", x->k, (char)x->color);
    //}
    void Print(Node * x = nullptr, int w = 79, int ll = 10)
    {
        x = x ? x : root;
        for (int l = 0; l < ll; l++)
        {
            bool e = false;
            CMaaString str = Print(x, w, l, &e);
            if  (e)
            {
                break;
            }
            __utf8_printf("%S\n", &str);
        }
    }
    CMaaString Print(Node * x, int w = 79, int l = 0, bool *e = nullptr)
    {
        if  (e)
        {
            *e = false;
        }
        if  (x == _nil)
        {
            CMaaString sp(nullptr, w);
            sp.Fill(' ');
            if  (e)
            {
                *e = true;
            }
            return sp;
        }
        if  (l == 0)
        {
            CMaaString Ret = Node2Text(x);
            //Ret.Format("%d%c", x->k, (char)x->color);
            int w2 = w - Ret.Length();
            if  (w2 < 2)
            {
                w2 = 2;
            }
            int w1 = w2 / 2;
            w2 -= w1;
            CMaaString sp1(nullptr, w1), sp2(nullptr, w2);
            sp1.Fill(' ');
            sp2.Fill(' ');
            return sp1 + Ret + sp2;
        }
        if  (x->left != _nil && x->left->p != x)
        {
            static char err[512];
            sprintf(err, "chk: %d->left error", x->k);
            throw err;
        }
        if  (x->right != _nil && x->right->p != x)
        {
            static char err[512];
            sprintf(err, "chk: %d->right error", x->k);
            throw err;
        }
        bool ee[2];
        CMaaString Ret =
        Print(x->left, w / 2, l - 1, &ee[0]) +
        Print(x->right, w - w / 2, l - 1, &ee[1]);
        if  (e)
        {
            *e = ee[0] && ee[1];
        }
        return Ret;
    }
};

//template<> CMaaFixedAllocator<CMaaRBTree<int, int>::Node> * CMaaRBTree<int, int>::Node::s_pAllocator = nullptr;
//template<> CMaaFixedAllocatorCreatorUl<CMaaRBTree<int, int>::Node> CMaaRBTree<int, int>::Node::s_AllocatorCreator(&CMaaRBTree<int, int>::Node::s_pAllocator);
// or
//DEF_ALLOCATOR_CMaaRBTree(int, int)
//opt:
//template<> CMaaString CMaaRBTree<int, int>::Node2Text(CMaaRBTree<int, int>::Node* x)
//{
//    return CMaaString::sFormat("%d%c", x->k, (char)x->color);
//}

#if 0
//template<> CMaaFixedAllocator<CMaaRBTree<int, int>::Node> * CMaaRBTree<int, int>::Node::s_pAllocator = nullptr;
//template<> CMaaFixedAllocatorCreatorUl<CMaaRBTree<int, int>::Node> CMaaRBTree<int, int>::Node::s_pAllocatorCreator(&CMaaRBTree<int, int>::Node::s_pAllocator);
DEF_ALLOCATOR_CMaaRBTree(int, int)

int gii = 0;
int test2()
{
    try
    {
        for (int c = 0; c < 1; c++)
        {
            //__utf8_printf("%79s\rc=%d  ", "", c);
            __utf8_printf("\rc=%d  ", c);
            const int N = 10000;
            const int VMax = 2 * N - N + N / 2;
            const int Dups = 1000;
            CMaaPtr<int> x(N);
            CMaaUnivHash<int, int> h;
            int i, j;
            __utf8_printf("gen ");
            for (i = 0; i < N; i++)
            {
                while(1)
                {
                    unsigned r = -1;
                    GetRnd(&r, sizeof(r));
                    //x[i] = rand() % VMax;
                    x[i] = i;//r % VMax;
                    //if (!h.Add(x[i], i))
                    {
                        break;
                    }
                }
            }
            __utf8_printf("shuff ");
            for (i = 0; i < N; i++)
            {
                unsigned r = 0;
                GetRnd(&r, sizeof(r));
                r %= N;
                int tmp = x[i];
                x[i] = x[(int)r];
                x[(int)r] = tmp;
            }
            CMaaRBTree<int, int> t;
            __utf8_printf("ins ");
            for (j = 0; j < Dups; j++)
            for (i = 0; i < N; i++)
            {
                if  (i % 1000 == 0)
                {
                    //__utf8_printf("\ri[%d]=%d:", i, x[i]);
                }
                /*
                 if (i >= 4)
                 {
                    gii++;
                 }
                 */
                t.Insert(x[i],i);

                if  (i % 10 == 0 && i > 0 && false)
                {
                    int xx = t.Remove(x[i - 10]);
                    x[i - 10] = -1;
                    //__utf8_printf("\ri[%d]=%d:", i, x[i]);
                }
                //t.Print();
                //getch();
            }

            __utf8_printf("LQ ");

            for (i = -1; i <= N; i++)
            {
                /*if (x[i] == -1)
                 {
                     continue;
                 }*/
                if  (i % 1000 == 0)
                {
                    //__utf8_printf("\rf[%d]=%d:", i, x[i]);
                }
                int k = -1, d = -1, r = -1;
                if  ((r = t.FindLQ(i, &k, &d)) || k != i)
                {
                    if  (i == -1 && r == 1)
                    {
                    }
                    else if (i == N && r == 0 && k == N - 1)
                    {
                    }
                    else
                    {
                        __utf8_printf("fLQ[%d]:%d %d ", i, r, k);
                    }
                    //__utf8_printf("-err\n");
                }
            }

            __utf8_printf("GQ ");

            for (i = -1; i <= N; i++)
            {
                /*if (x[i] == -1)
                 {
                     continue;
                 }*/
                if  (i % 1000 == 0)
                {
                    //__utf8_printf("\rf[%d]=%d:", i, x[i]);
                }
                int k = -1, d = -1, r = -1;
                if  ((r = t.FindGQ(i, &k, &d)) || k != i)
                {
                    if  (i == N && r == 1)
                    {
                    }
                    else if (i == -1 && r == 0 && k == 0)
                    {
                    }
                    else
                    {
                        __utf8_printf("fGQ[%d]:%d %d ", i, r, k);
                    }
                }
            }

            __utf8_printf("LnQ ");

            for (i = -1; i <= N + 1; i++)
            {
                /*if (x[i] == -1)
                 {
                     continue;
                 }*/
                if  (i % 1000 == 0)
                {
                    //__utf8_printf("\rf[%d]=%d:", i, x[i]);
                }
                int k = -1, d = -1, r = -1;
                if  ((r = t.FindLnQ(i, &k, &d)) || k != i - 1)
                {
                    if  ((i == -1 || i == 0) && r == 1)
                    {
                    }
                    else if (i == N + 1 && r == 0 && k == N - 1)
                    {
                    }
                    else
                    {
                        __utf8_printf("fLnQ[%d]:%d %d ", i, r, k);
                    }
                }
            }

            __utf8_printf("GnQ ");

            for (i = -2; i <= N; i++)
            {
                /*if (x[i] == -1)
                 {
                     continue;
                 }*/
                if  (i % 1000 == 0)
                {
                    //__utf8_printf("\rf[%d]=%d:", i, x[i]);
                }
                int k = -1, d = -1, r = -1;
                if  ((r = t.FindGnQ(i, &k, &d)) || k != i + 1)
                {
                    if  ((i == N -1 || i == N) && r == 1)
                    {
                    }
                    else if (i == -2 && r == 0 && k == 0)
                    {
                    }
                    else
                    {
                        __utf8_printf("fGnQ[%d]:%d %d ", i, r, k);
                    }
                }
            }

            __utf8_printf("Succ ");

            for (i = -1; i <= N; i++)
            {
                /*if (x[i] == -1)
                 {
                     continue;
                 }*/
                if  (i % 1000 == 0)
                {
                    //__utf8_printf("\rf[%d]=%d:", i, x[i]);
                }
                int k = -1, d = -1, r = -1;
                if  ((r = t.FindSucc(i, &k, &d)) || (k != i + 1 && Dups == 1) || (k != i + 1 && k != i && Dups > 1))
                {
                    if  ((i == -1 || i == N) && r == 1)
                    {
                    }
                    else if (i == N - 1 && r == 2)
                    {
                    }
                    else
                    {
                        __utf8_printf("Succ[%d]:%d ", i, r);
                    }
                }
            }

            __utf8_printf("Pred ");

            for (i = -1; i <= N; i++)
            {
                /*if (x[i] == -1)
                 {
                     continue;
                 }*/
                if  (i % 1000 == 0)
                {
                    //__utf8_printf("\rf[%d]=%d:", i, x[i]);
                }
                int k = -1, d = -1, r = -1;
                if  ((r = t.FindPred(i, &k, &d)) || (k != i - 1 && Dups == 1) || (k != i - 1 && k != i && Dups > 1))
                {
                    if  ((i == -1 || i == N) && r == 1)
                    {
                    }
                    else if (i == 0 && r == 2)
                    {
                    }
                    else
                    {
                        __utf8_printf("Pred[%d]:%d ", i, r);
                    }
                }
            }

            if  (0)
            {
                __utf8_printf("\n");
                int a = N / 2;
                // a = 0;
                // a = N - 1;
                CMaaRBTree<int, int>::Handle h = t.FindNode(a), h1, h2;
                __utf8_printf("%p %d %d\n", h, t.k(h), t.d(h));
                h1 = h2 = h;
                for (i = 0; i < Dups + 1; i++)
                {
                    h1 = t.FindSucc(h1);
                    __utf8_printf("Succ %p %d %d\n", h1, h1 ? t.k(h1) : -9999, h1 ? t.d(h1) : -8888);
                }
                for (i = 0; i < Dups + 1; i++)
                {
                    h2 = t.FindPred(h2);
                    __utf8_printf("Pred %p %d %d\n", h2, h2 ? t.k(h2) : -9999, h2 ? t.d(h2) : -8888);
                }
            }

            //__utf8_printf("\n");
            //t.Print();
            __utf8_printf("find ");
            for (i = 0; i < N; i++)
            {
                if  (x[i] == -1)
                {
                    continue;
                }
                if  (i % 1000 == 0)
                {
                    //__utf8_printf("\rf[%d]=%d:", i, x[i]);
                }
                int ii = -1;
                if  (t.Find(x[i], &ii))// || ii != i)
                {
                    __utf8_printf("\rf[%d]=%d:", i, x[i]);
                    __utf8_printf("-err\n");
                }
            }
            //__utf8_printf("\n");
            __utf8_printf("shuff ");
            for (i = 0; i < N; i++)
            {
                unsigned r = 0;
                GetRnd(&r, sizeof(r));
                r %= N;
                int tmp = x[i];
                x[i] = x[(int)r];
                x[(int)r] = tmp;
            }
            __utf8_printf("find ");
            for (i = 0; i < N; i++)
            {
                if  (x[i] == -1)
                {
                    continue;
                }
                if  (i % 1000 == 0)
                {
                    //__utf8_printf("\rf[%d]=%d:", i, x[i]);
                }
                int ii = -1;
                if  (t.Find(x[i], &ii))// || ii != i)
                {
                    __utf8_printf("\rf[%d]=%d:", i, x[i]);
                    __utf8_printf("-err\n");
                }
            }
            __utf8_printf("rem ");
            for (j = 0; j < Dups; j++)
            for (i = 0; i < N; i++)
            {
                if  (x[i] == -1)
                {
                    continue;
                }
                //__utf8_printf("r %d: ", i);
                if  (i % 1000 == 0)
                {
                    //__utf8_printf("\rr[%d]=%d:", i, x[i]);
                }
                if  (i >= 3)
                {
                    gii++;
                }
                int xx = t.Remove(x[i]);
                //__utf8_printf("%d\n", x);
                if  (xx)
                {
                    __utf8_printf("\rr[%d]=%d:", i, x[i]);
                    __utf8_printf("-err\n");
                }
                else
                {
                    //__utf8_printf("\n");
                }

                //t.Print();
                //getch();
            }
            //__utf8_printf("\n");
            //__utf8_printf("delete array\n");
            //delete [] x;
            __utf8_printf("Empty:\r");
            t.Print();
            //__utf8_printf("\n");
        }
        __utf8_printf("\n");
        return 0;
    }
    catch(CMaaString e)
    {
        __utf8_printf("Error: %s\n", (const char *)e);
    }
    catch(const char * e)
    {
        __utf8_printf("Error: %s\n", e);
    }
    catch(...)
    {
        __utf8_printf("catch(...)\n");
    }
    return 1;
}

int test1()
{
    try
    {
        for (int c = 0; c < 10000; c++)
        {
            __utf8_printf("%79s\rc=%d  ", "", c);
            const int N = 100;
            const int VMax = 2 * N - N + N / 2;
            CMaaPtr<int> x(N);
            CMaaUnivHash<int, int> h;
            int i;
            __utf8_printf("gen rand  ");
            for (i = 0; i < N; i++)
            {
                while(1)
                {
                    unsigned r = -1;
                    GetRnd(&r, sizeof(r));
                    //x[i] = rand() % VMax;
                    x[i] = r % VMax;
                    //if (!h.Add(x[i], i))
                    {
                        break;
                    }
                }
            }
            CMaaRBTree<int, int> t;
            __utf8_printf("insert/remove ");
            for (i = 0; i < N; i++)
            {
                if  (i % 1000 == 0)
                {
                    //__utf8_printf("\ri[%d]=%d:", i, x[i]);
                }
                /*
                 if (i >= 4)
                 {
                    gii++;
                 }
                 */
                t.Insert(x[i],i);

                if  (i % 10 == 0 && i > 0)
                {
                    int xx = t.Remove(x[i - 10]);
                    x[i - 10] = -1;
                    //__utf8_printf("\ri[%d]=%d:", i, x[i]);
                }
                //t.Print();
                //getch();
            }
            //__utf8_printf("\n");
            //t.Print();
            __utf8_printf("find ");
            for (i = 0; i < N; i++)
            {
                if  (x[i] == -1)
                {
                    continue;
                }
                if  (i % 1000 == 0)
                {
                    //__utf8_printf("\rf[%d]=%d:", i, x[i]);
                }
                int ii = -1;
                if  (t.Find(x[i], &ii))// || ii != i)
                {
                    __utf8_printf("\rf[%d]=%d:", i, x[i]);
                    __utf8_printf("-err\n");
                }
            }
            //__utf8_printf("\n");
            __utf8_printf("shuffle ");
            for (i = 0; i < N; i++)
            {
                unsigned r = 0;
                GetRnd(&r, sizeof(r));
                r %= N;
                int tmp = x[i];
                x[i] = x[(int)r];
                x[(int)r] = tmp;
            }
            __utf8_printf("find ");
            for (i = 0; i < N; i++)
            {
                if  (x[i] == -1)
                {
                    continue;
                }
                if  (i % 1000 == 0)
                {
                    //__utf8_printf("\rf[%d]=%d:", i, x[i]);
                }
                int ii = -1;
                if  (t.Find(x[i], &ii))// || ii != i)
                {
                    __utf8_printf("\rf[%d]=%d:", i, x[i]);
                    __utf8_printf("-err\n");
                }
            }
            __utf8_printf("remove ");
            for (i = 0; i < N; i++)
            {
                if  (x[i] == -1)
                {
                    continue;
                }
                //__utf8_printf("r %d: ", i);
                if  (i % 1000 == 0)
                {
                    //__utf8_printf("\rr[%d]=%d:", i, x[i]);
                }
                if  (i >= 3)
                {
                    gii++;
                }
                int xx = t.Remove(x[i]);
                //__utf8_printf("%d\n", x);
                if  (xx)
                {
                    __utf8_printf("\rr[%d]=%d:", i, x[i]);
                    __utf8_printf("-err\n");
                }
                else
                {
                    //__utf8_printf("\n");
                }

                //t.Print();
                //getch();
            }
            //__utf8_printf("\n");
            //__utf8_printf("delete array\n");
            //delete [] x;
            __utf8_printf("Empty:\r");
            t.Print();
            //__utf8_printf("\n");
        }
        __utf8_printf("\n");
        return 0;
    }
    catch(CMaaString e)
    {
        __utf8_printf("Error: %s\n", (const char *)e);
    }
    catch(const char * e)
    {
        __utf8_printf("Error: %s\n", e);
    }
    catch(...)
    {
        __utf8_printf("catch(...)\n");
    }
    return 1;
}

int fix_12_03_2022()
{
    CMaaRBTree<int, int> t;
    t.Add(5, 51);
    t.Add(5, 52);
    t.Add(5, 53);
    t.Add(5, 54);
    t.Add(5, 55);
    t.Add(1, 11);
    t.Add(10, 101);
    t.Print();
    //int l = 6, g = 4;
    int l = 5, g = 5;
    CMaaRBTree<int, int>::Handle h = t.TreeSearchLQ(l);
    if  (h != t.begin() && h->c_key() != l)
    {
        __utf8_printf("%d ", h->c_data());
    }
    //while (h != t.begin() && h->k == l)
    while(h != t.begin() && h->c_key() == l)
    {
        __utf8_printf("%d ", h->c_data());
        h = t.TreePredecessor(h);
    }
    __utf8_printf("\n");
    h = t.TreeSearchGQ(g);
    if  (h != t.end() && h->c_key() != g)
    {
        __utf8_printf("%d ", h->c_data());
    }
    //while (h != t.end() && h->k == g)
    while(h != t.end() && h->c_key() == g)
    {
        __utf8_printf("%d ", h->c_data());
        h = t.TreeSuccessor(h);
    }
    __utf8_printf("\n");
    return 0;
}

#endif

//template<> CMaaFixedAllocator<CMaaRBTree<int, int>::Node> * CMaaRBTree<int, int>::Node::s_pAllocator = nullptr;
//template<> CMaaFixedAllocatorCreatorUl<CMaaRBTree<int, int>::Node> CMaaRBTree<int, int>::Node::s_AllocatorCreator(&CMaaRBTree<int, int>::Node::s_pAllocator);
// or
//DEF_ALLOCATOR_CMaaRBTree(int, int)
